#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define MP(x,y) make_pair(x,y)
typedef pair<int,int> PII;

class Grids
{
public:
        Grids(int, int);
        void add(int x, int y, int h) { grids[x][y] = h; }
        int getVolume();
        ~Grids();
private:
        int **grids;
        int nRow, nCol;
        priority_queue<pair<int, PII> > q;
        vector< vector<bool> > used;
        int floodfill(int, int, int);
        inline bool check(int x, int y) { return (x<0||x>=nRow||y<0||
y>=nCol); }};

Grids::Grids(int n, int m)
{
        nRow = n; nCol = m;
        grids = new int* [n];
        int i, j;
        for(i = 0; i < n; i++) {
                grids[i] = new int[m];
                memset(grids[i], 0, sizeof(int)*m);
        }}

int Grids::getVolume()
{
        int i, j;
        int ret = 0;
        used.clear();
        for(i = 0; i < nRow; i++) {
                vector<bool> v;
                for(j = 0; j < nCol; j++)
                        v.push_back(0);
                used.push_back(v);
        }
        for(i = 0; i < nCol - 1; i++)
                q.push(MP(-grids[0][i], MP(0, i)));
        for(i = 0; i < nRow - 1; i++)
                q.push(MP(-grids[i][nCol-1], MP(i, nCol-1)));
        for(i = nCol-1; i > 0; i--)
                q.push(MP(-grids[nRow-1][i], MP(nRow-1, i)));
        for(i = nRow-1; i > 0; i--)
                q.push(MP(-grids[i][0], MP(i, 0)));
        while(!q.empty()) {
                int x = q.top().second.first;
                int y = q.top().second.second;
                int h = q.top().first;
                q.pop();
                if(used[x][y]) continue;
                ret += floodfill(x, y, -h);
        }
        return ret;}

int Grids::floodfill(int x, int y, int h)
{
        int dx[4] = {-1, 0, 0, 1};
        int dy[4] = {0, -1, 1, 0};
        int i, j;
        int ret = h - grids[x][y];
        used[x][y] = true;
        for(i = 0; i < 4; i++) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if(check(tx, ty) || used[tx][ty])
                        continue;
                if(grids[tx][ty] <= h)
                        ret += floodfill(tx, ty, h);
                else q.push(MP(-grids[tx][ty], MP(tx, ty)));
        }
        return ret;}

Grids::~Grids()
{
        for(int i = 0; i < nRow; i++)
                delete [] grids[i];
        delete [] grids;}

int main()
{
        Grids g(3, 3);
        int i, j;
        int a[][3] = { {5, 5, 5}, {5, 1, 2}, {5, 5, 5}};
        for(i = 0; i < 3; i++)
                for(j = 0; j < 3; j++)
                        g.add(i, j, a[i][j]);

        cout << g.getVolume() << endl;
        int b[][3] = { {5, 5, 5}, {5, 0, 0}, {5, 5, 5}};
        for(i = 0; i < 3; i++)
                for(j = 0; j < 3; j++)
                        g.add(i, j, b[i][j]);
        cout << g.getVolume() << endl;
        int c[][9] = {
        {1,2,3,4, 4,3, 3,2,2},
        {2,6,9,10,6,7, 7,7,3},
        {2,3,8,5, 6,9, 3,5,3},
        {2,4,1,4, 3,8, 3,7,3},
        {2,4,2,4, 5,10,3,7,5},
        {2,4,2,2, 1,9, 3,3,1},
        {1,3,3,3, 3,3, 5,3,2},
        {1,1,1,2, 2,2, 4,2,1}
        };
        Grids gc(8, 9);
        for(i = 0; i < 8; i++)
                for(j = 0; j < 9; j++)
                        gc.add(i, j, c[i][j]);
        cout << gc.getVolume() << endl;
        Grids gd(4, 5);
        int d[][5] = {
                {3,4,4,4,5},
                {4,2,1,2,4},
                {4,0,2,2,4},
                {5,5,4,4,6}
        };
        for(i = 0; i < 4; i++)
                for(j = 0; j < 5; j++)
                        gd.add(i, j, d[i][j]);
        cout << gd.getVolume() << endl;
        return 0;

}
